#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/23
# @Author   :Changshu
# @File     :Exercise_628.py
# 628. 三个数的最大乘积
# 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

# 注意：
# 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
# 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

# 找到最大的三个数和最小的两个数，因为负数乘以负数为正数
class Solution:
	'''法一：排序
	def maximumProduct(self, nums: list) -> int:
		nums.sort()
		max1,max2,max3=nums[-1],nums[-2],nums[-3]
		min1,min2=nums[0],nums[1]
		if max1>0 and min1*min2>max2*max3:
			return max1*min1*min2
		return max1*max2*max3
	'''

	'''法二：线性查找'''
	def maximumProduct(self, nums: list) -> int:
		max1,max2,max3=-10**5,-10**5,-10**5
		min1,min2=10**5,10**5
		for n in nums:
			if n>max1:
				max3=max2
				max2=max1
				max1=n
			elif n>max2:
				max3=max2
				max2=n
			elif n>max3:
				max3=n
			if n<min1:
				min2=min1
				min1=n
			elif n<min2:
				min2=n
		if max1 > 0 and min1 * min2 > max2 * max3:
			return max1 * min1 * min2
		return max1 * max2 * max3

if __name__ == '__main__':
	solution=Solution()
	nums=[2,1,4,3,9,10,-4,-9,-8]
	# nums=[-1,-2,-3,-4]
	print(solution.maximumProduct(nums))

